package algorithm

import "fmt"

// 全排列算法-不可重复的数组
func overArrange(arr, s []int, cur int) {
	if len(s) == cur {
		fmt.Println(arr)
		return
	}
	for _, b := range s {
		flag := false
		for i := 0; i < cur; i++ {
			if arr[i] == b {
				flag = true
				break
			}
		}
		if !flag {
			arr[cur] = b
			overArrange(arr, s, cur+1)
		}
	}
}
func maxSubArray(nums []int) int {
	ans, cur := nums[0], nums[0]
	if len(nums) == 1 {
		return ans
	}
	max := func(a, b int) int {
		if a > b {
			return a
		}
		return b
	}
	for i := 1; i < len(nums); i++ {
		ans = max(ans+nums[i], nums[i])
		cur = max(ans, cur)
	}
	return cur
}

// 可重复数组的全排列
func overArrangev2(nums []int) [][]int {
	res := [][]int{}
	dfs(nums, &res, 0)
	return res
}

func dfs(nums []int, res *[][]int, index int) {
	if index == len(nums) {
		*res = append(*res, dump(nums))
	}

	m := map[int]int{}
	for i := index; i < len(nums); i++ {
		if _, ok := m[nums[i]]; ok {
			continue
		}
		nums[i], nums[index] = nums[index], nums[i]
		dfs(nums, res, index+1)
		nums[i], nums[index] = nums[index], nums[i]
		m[nums[i]] = 1
	}
}

func dump(a []int) []int {
	b := make([]int, len(a))
	copy(b, a)
	return b
}

func isSwap(arr []int, i, j int) bool {
	// for k := i; k < j; k++ {
	// 	if arr[k] == arr[j] {
	// 		return false
	// 	}
	// }
	// return true
	if i != j {
		if arr[i] == arr[j] {
			return false
		}
	}
	return true
}

func RunOverArrange() {
	case1 := []int{1, 2, 3, 67, 76}
	fmt.Println("运行新算法啦！！！全排列算法😯！！")
	pre := make([]int, len(case1), len(case1))
	overArrange(pre, case1, 0)
	fmt.Println(pre)
	// res := overArrangev2(case1)
	// fmt.Println(case1)
	// fmt.Println(res)
}

var res [][]int

func subarr(arr, path []int, cur int, res *[][]int) {
	if len(arr) == cur {
		dst := make([]int, len(arr))
		copy(dst, path)
		*res = append(*res, dst)
		return
	}
	for _, val := range arr {
		flag := false
		for i := 0; i < cur; i++ {
			if val == path[i] {
				flag = true
				break
			}
		}
		if !flag {
			path[cur] = val
			subarr(arr, path, cur+1, res)
		}
	}

}
func TestSubarr() {
	case1 := []int{3, 4, 5, 67, 2}
	res = make([][]int, 0)
	path := make([]int, len(case1), len(case1))
	subarr(case1, path, 0, &res)
	fmt.Println(res)
	// fmt.Println(path)
}
